Air Malawi được thành lập bởi 1 đạo luật của quốc hội Malawi và bắt đầu hoạt động từ 1.9.1967. Air Malawi là hãng kế tục của một hãng cùng tên được thành lập năm 1964 như một hãng phụ thuộc của Central African Airways với 2 máy bay "C-47 Dakotas" và 3 máy bay "de Havilland DHC-2 Beavers". Sau đó là 1 máy bay BAC 1-11-475 bay tuyến đường trong vùng tớiHarare, Johannesburg và Nairobi. Năm 1974 hãng bắt đầu mở tuyến bay tới Sân bay London Gatwick bằng 1 máy bay Vickers VC-10, nhưng đến cuối thập niên 1970 thì ngưng. Hãng dùng các máy bay Short Skyvan, Britten-Norman Islander và Hawker Siddeley HS-748 cho các tuyến bay trong vùng. Trong thập niên 1990 các máy bay đó được thay thế bởi các máy bay Dornier 228 và ATR 42. Năm 1985 hãng thuê 1 máy bay Boeing 747SP dành cho các nhân vật quan trọng (VIP) trong chính phủ.